
public class BinarySearchTree {
    static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        public TreeNode(int val){
            this.val = val;
        }
    }
    TreeNode root = null;
    //查找结点
    public TreeNode sreach(int key){
        TreeNode cur = root;
        while(cur != null){
            if(cur.val > key){
                cur = cur.left;
            }else if(cur.val < key){
                cur = cur.right;
            }else{
                return cur;
            }
        }
        return null;
    }
    //插入结点
    public boolean insert(int key){
        if(root == null){
            root = new TreeNode(key);
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = root;
        while(cur != null){
            parent = cur;
            if(cur.val > key){
                cur = cur.left;
            }else if(cur.val < key){
                cur = cur.right;
            }else{
                return false;
            }
        }
        if(parent.val > key){
            parent.left = new TreeNode(key);
        }else{
            parent.right = new TreeNode(key);
        }
    return true;
    }
    //删除结点
    public void remove(int key){
        TreeNode cur = root;
        TreeNode parent = root;
        while(cur != null){
            if(cur.val > key){
                parent = cur;
                cur = cur.left;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }
            else{//找到了,并删除
                removeNode(cur,parent);
                return;
            }
        }
    }
    private void removeNode(TreeNode cur, TreeNode parent){
        //分三大种情况: 1.cur.left == null
        if(cur.left == null){
            if(cur == root){
                root = cur.right;
            }else if(parent.left == cur){
                parent.left = cur.right;
            }else if(parent.right == cur){
                parent.right = cur.right;
            }
            //第二大种情况:2.cur.right == null
        }else if(cur.right == null){
            if(cur == root){
                root = cur.left;
            }else if(parent.left == cur){
                parent.left = cur.left;
            }else if(parent.right == cur){
                parent.right = cur.left;
            }
        }
        else{
            /**
             * 第三大种情况：cur两边都不为空
             * 可以使用替换法进行删除，有以下两种替换方式（任意一种即可）
             * 1.在cur的右边找最小值，并且若能找到这个最小值，这个最小值点一定不存在左子树
             * 2.在cur的左边找最大值，并且若能找到这个最小值，这个最大值点一定不存在右子树
             * 以下代码通过方法1实现
             * 通过target和targetParent来确定要替换的结点
             */
            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            while(target.left != null){
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            //分两种情况
            if(targetParent.left == target){
                targetParent.left = target.right;
            }else{
                targetParent.right = target.right;
            }
        }
    }
    //中序遍历打印二叉树
    public void Print(TreeNode root){
        if(root == null){
            return;
        }
        Print(root.left);
        System.out.print(root.val);
        Print(root.right);
    }
}
